package com.changanw.code05;



/**
 * @author changanw
 * @version ncc1.0
 * @description 第五题 最长回文子串，给你一个字符串 s，找到 s 中最长的回文子串。
 * 输入：s = "cbbd"
 * 输出："bb"
 * @date 2023/6/25 21:08
 */
public class Code05 {
  public String longestPalindrome(String s) {
    int length = s.length();
    if (length < 2){
      return s;
    }
    int maxLen = 1;
    int begin = 0;
    char[] charArray = s.toCharArray();
    //通过双层for循环取出所有子串，通过validPalindromic方法判断是不是回文子串
    for (int i = 0; i < length - 1; i++) {
      for (int j = i + 1; j < length; j++) {
        if (j - i + 1 > maxLen && validPalindromic(charArray,i,j)){
          //子串的最大长度  例如[a,b,a], 开始是0，结束是2，整个子串的长度是 2-0+1
          maxLen = j - i + 1;
          begin = i;
        }

      }
    }

    /*int start = 0, end = 0, n = s.length();
    int i = 0;
    while (i < n) {
      int left = i, right = i;
      //如果后面有连续相同字符，把right向右扩展到最后一个相同字符的位置，
      //并把i设置到该位置的下一个位置。
      //因为每次循环i左边的字符一定和i不相同，所以不需要将left向左扩展
      while (right < n - 1 && s.charAt(right + 1) == s.charAt(left)) {
        right++;
      }
      i = right + 1;

      while (left > -1 && right < n && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
      }
      if (right - left - 1> end - start) {
        end = right;
        start = left + 1;
      }
    }*/
    return s.substring(begin, begin+maxLen);
  }
  private boolean validPalindromic(char[] chars,int left,int right){
    while (left < right){
      if (chars[left] != chars[right]){
        return false;
      }
      left++;
      right--;
    }
    return true;

  }

  public static void main(String[] args) {
    Code05 code05 = new Code05();
    String a = code05.longestPalindrome("ab");
    System.out.println(a);
  }
}
